package com.wujunshen.algorithm.leetcode.divide.conquer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/1 11:11<br>
 */
@Slf4j
public class 合并k个已排序的链表 {

  public static void main(String[] args) {
    List<ListNode> lists = new ArrayList<>();
    lists.add(new ListNode(4, new ListNode(5, new ListNode(1))));
    lists.add(new ListNode(1, new ListNode(3, new ListNode(4))));
    lists.add(new ListNode(2, new ListNode(6)));
    ListNode result = mergeLists(lists);

    int index = 0;
    while (result != null && result.next != null) {
      log.info("index {} value is:{}", index, result);
      result = result.next;
      index++;
    }
  }

  /**
   * k个链表归并排序
   *
   * @param lists
   * @return
   */
  private static ListNode mergeLists(List<ListNode> lists) {
    if (lists == null || lists.isEmpty()) {
      return null;
    }

    PriorityQueue<ListNode> queue =
        new PriorityQueue<>(lists.size(), Comparator.comparingInt(o -> o.val));

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    for (ListNode node : lists) {
      if (node != null) {
        queue.add(node);
      }
    }

    while (!queue.isEmpty()) {
      tail.next = queue.poll();
      tail = tail.next;

      if (tail.next != null) {
        queue.add(tail.next);
      }
    }
    return dummy.next;
  }

  @Data
  @NoArgsConstructor
  @AllArgsConstructor
  static class ListNode {
    int val;
    ListNode next;

    ListNode(int value) {
      this.val = value;
    }
  }
}

class Solution {
  public 合并k个已排序的链表.ListNode mergeKLists(ArrayList<合并k个已排序的链表.ListNode> lists) {
    if (lists == null || lists.isEmpty()) {
      return null;
    }

    PriorityQueue<合并k个已排序的链表.ListNode> queue =
        new PriorityQueue<>(lists.size(), Comparator.comparingInt(o -> o.val));

    合并k个已排序的链表.ListNode dummy = new 合并k个已排序的链表.ListNode(0);
    合并k个已排序的链表.ListNode tail = dummy;

    for (合并k个已排序的链表.ListNode node : lists) {
      if (node != null) {
        queue.add(node);
      }
    }

    while (!queue.isEmpty()) {
      tail.next = queue.poll();
      tail = tail.next;

      if (tail.next != null) {
        queue.add(tail.next);
      }
    }
    return dummy.next;
  }
}
